package codeRandomThoughts.Test216组合总和III;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        int sum = 0;
        int startIndex = 1;
        backtracking(n, k, sum, startIndex);
        return result;
    }

    public void backtracking(int targetSum, int k, int sum, int startIndex) {
        //剪枝操作
        if (sum > targetSum) {
            return;
        }

        //终止条件
        if (path.size() == k) {
            if (sum == targetSum) {
                result.add(new ArrayList<>(path));
            }
            return;//如果和不等于sum就直接返回
        }

        //因为集合里面总共就9个数,所以for循环固定i<=9
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            sum += i;
            path.add(i);
            backtracking(targetSum, k, sum, i + 1);//每往下一层 startIndex就加一
            sum -= i;
            path.remove(path.size() - 1);
        }
    }
}
